package com.example.demo.leetcode.classics150;

import java.util.*;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _91克隆图
 * @description
 * @date 2023/08/07 16:11
 * <p>
 * ******************************************************
 */
public class _91克隆图 {

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Map<Integer, Node> valueToObject = new HashMap<>();
        dfs(node, valueToObject);
        Node newNode = valueToObject.get(node.val);
        Set<Integer> visited = new HashSet<>();
        visited.add(newNode.val);
        clone(node, newNode, valueToObject, visited);
        return newNode;
    }

    private void clone(Node node, Node newNode, Map<Integer, Node> valueToObject, Set<Integer> visited) {
        for (Node neighbor : node.neighbors) {
            newNode.neighbors.add(valueToObject.get(neighbor.val));
            if (visited.add(neighbor.val)) {
                clone(neighbor, valueToObject.get(neighbor.val), valueToObject ,visited);
            }
        }
    }

    private void dfs(Node node, Map<Integer, Node> valueToObject) {
        Node newNode = new Node(node.val);
        valueToObject.put(node.val, newNode);

        for (Node neighbor : node.neighbors) {
            if (!valueToObject.containsKey(neighbor.val)) {
                dfs(neighbor, valueToObject);
            }
        }
    }


    class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }
}
